Euclidean Algorithm

The Euclidean Algorithm is a procedure for finding the greatest common divisor of a pair of integers.

We will use the following result here throughout.

Theorem

For integers \(a\) and \(b\) with \(b \neq 0\), if the division algorithm for integers is applied as follows

\[ a = bq + r,\]

then \(\gcd(a, b) = \gcd(b, r)\).

The Euclidean Algorithm proceeds to calculate the greatest common divisor of two integers \(a\) and \(b\) by repeatedly applying the division algorithm to the divisor and remainder of the previous division, using the above lemma. This is best illustrated through an example.

Consider the greatest common divisor of \(53\) and \(124\).

We find apply the division algorithm for integers to \(a = 124\) and \(b = 53\):

We then repeatedly apply the division algorithm to the divisor and remainder:

Since \(\gcd(1, 0) = 1\) is trivial, we can then iteratively conclude that this is the greatest common divisor of the quotient and remainder of each division step, and therefore the greatest common divisor of the original two numbers.

Implementation

let rec gcd a b =
    // Division algorithm
    let r = (a % b + b) % b
    let q = (a - r) / b

    if r <> 0 then
        gcd b r
    else
        b

printfn "%d" (gcd 7 255)